% Ejercicio "Gramática"
\subsection*{\fbox{\theejercicio} - Gram\'atica}

Sea la gram\'atica:

\begin{center}
\begin{tabular}{|lcl|} \hline
         &               &                 \\
{\em S'} & $\rightarrow$ & {\em S}{\bf \$} \\
{\em S}  & $\rightarrow$ & {\bf a}{\em SA} \\
{\em S}  & $\rightarrow$ & $\varepsilon$\  \\
{\em A}  & $\rightarrow$ & {\em B}{\bf b}  \\
{\em B}  & $\rightarrow$ & {\em A}{\bf c}  \\
{\em B}  & $\rightarrow$ & $\varepsilon$\  \\
         &               &                 \\ \hline
\end{tabular} 
\end{center}

\begin{enumerate}[1)]
\item Demostrar que esta gram\'atica no es LL(1).
\item Construir una gram\'atica equivalente que sea LL(1) y construir para ella las tablas de an\'alisis.
\end{enumerate}

% Solución del ejercicio
\subsubsection*{SOLUCI\'ON}

Apartado 1)

La gram\'atica no cumple la condici\'on LL(1), ya que para el s\'{\i}mbolo terminal {\em B}, existen dos reglas cuyos conjuntos de s\'{\i}mbolos directores tienen elementos comunes:

\begin{list}{}{}
\item  $ SD(B \rightarrow Ac) = CAB(Ac \cdot SIG(B)) = CAB(A) =(CAB(B) - \{ \varepsilon \}) \cup \{b\} = \{b\} $
\item $ SD(B \rightarrow \varepsilon) = CAB(SIG(B)) = SIG(B) = \{b\} $
\end{list}

Apartado 2)

Una gram\'atica equivalente a la anterior se obtiene transformando la anterior. Para hallarla se sigue el siguiente proceso. Primero se elimina el s\'{\i}mbolo {\em A}, a fin de simplificar la gram\'atica:

\begin{center}
\begin{tabular}{lcl}
{\em S'} & $\rightarrow$ & {\em S}{\bf \$} \\
{\em S}  & $\rightarrow$ & {\bf a}{\em SA} \\
{\em S}  & $\rightarrow$ & $\varepsilon$\  \\
{\em A}  & $\rightarrow$ & {\em B}{\bf b}  \\
{\em B}  & $\rightarrow$ & {\em A}{\bf c}  \\
{\em B}  & $\rightarrow$ & $\varepsilon$\  \\
\end{tabular} 
\end{center}

A partir de esta gram\'atica es f\'acil demostrar que el lenguaje que se genera es:
$$ L(G) = \{ (a)^n((bc)^*b)^n | \ n \geq 0 \} $$

que tambi\'en puede expresarse como:
$$ L(G) = \{ (a)^n(b(cb)^*)^n | \ n \geq 0 \} $$

que puede ser generado mediante una gram\'atica equivalente a la anterior que cumple la condici\'on LL(1):

\begin{center}
\begin{tabular}{|lcl|} \hline
         &               &                              \\
{\em S'} & $\rightarrow$ & {\em S}{\bf \$}              \\
{\em S}  & $\rightarrow$ & {\bf a}{\em S}{\bf b}{\em B} \\
{\em S}  & $\rightarrow$ & $\varepsilon$\               \\
{\em B}  & $\rightarrow$ & {\bf cb}{\em B}              \\
{\em B}  & $\rightarrow$ & $\varepsilon$\               \\
         &               &                              \\ \hline
\end{tabular}
\end{center}

Esta gram\'atica es LL(1), ya que:

\begin{list}{}{}
\item $ SD(S \rightarrow aSBb) = CAB(aSBb \cdot SIG(S)) = \{a\} $
\item $ SD(S \rightarrow \varepsilon) = CAB(SIG(S)) = SIG(S) = \{\$\} \cup \{b\} = \{\$,b\} $
\item
\item $ SD(B \rightarrow cbB) = CAB(cbB \cdot SIG(B)) = \{c\} $
\item $ SD(B \rightarrow \varepsilon) = CAB(SIG(B)) = SIG(B) = SIG(S) =\{\$, b\} $
\end{list}

La tabla de an\'alisis LL(1) para esta gram\'atica es:

\begin{center}
\begin{tabular}{|l|cccc|} \hline
        & {\bf a}                      & {\bf b}       & {\bf c}         & {\bf \$}      \\ \hline
{\em S} & {\bf a}{\em S}{\bf b}{\em B} & $\varepsilon$ & $\varepsilon$   & $\varepsilon$ \\
{\em B} & \                            & $\varepsilon$ & {\bf cb}{\em B} & $\varepsilon$ \\ \hline
\end{tabular}
\end{center}